package leetcode.year2021.month11;

// 238. 除自身以外数组的乘积
public class _06_1ProductExceptSelf238 {
  //使用输出数组，先计算左边的乘积，再动态计算右边的结果，全程维护一个输出数组
  public int[] productExceptSelf(int[] nums) {
    int length = nums.length;
    int[] outputs = new int[length];
    outputs[0] = 1;
    for (int i = 1; i < nums.length; i++) {
      outputs[i] = outputs[i-1] * nums[i-1];
    }
    int temp = nums[length-1];
    for (int i = length - 2; i >= 0; i--) {
      outputs[i] = outputs[i] * temp;
      temp = temp * nums[i];
    }
    return outputs;
  }
  // 记录左右数组的乘积，三次遍历求取结果
//  public int[] productExceptSelf(int[] nums) {
//    int length = nums.length;
//    int[] output = new int[length];
//
//    //记录每个值左边的乘积
//    int[] leftTimes = new int[length];
//    leftTimes[0] = 1;
//    for (int i = 1; i < length; i++) {
//      leftTimes[i] = nums[i-1] * leftTimes[i-1];
//    }
//    // 记录每个值右边的乘积
//    int[] rightTimes = new int[length];
//    rightTimes[length-1] = 1;
//    for (int i = length-2; i >= 0; i--) {
//      rightTimes[i] = rightTimes[i+1] * nums[i+1];
//    }
//
//    // 第三次遍历，求取所有值的结果
//    for (int i = 0; i < length; i++) {
//      output[i] = leftTimes[i]*rightTimes[i];
//    }
//    return output;
//  }

  /**
   * 238. 除自身以外数组的乘积
   * 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
   *
   *
   *
   * 示例:
   *
   * 输入: [1,2,3,4]
   * 输出: [24,12,8,6]
   *
   *
   * 提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
   *
   * 说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
   *
   * 进阶：
   * 你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
   *
   * 通过次数144,833提交次数200,146
   */
}
